#include"BTree.h"
#include<stdio.h>
#include<string.h>
#include<malloc.h>
#include<assert.h>


//队列
QNode* buyNode(QDataType data) {
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (NULL == newNode) {
		assert(0);
	}
	newNode->data = data;
	newNode->next = NULL;
	return newNode;
}
//初始化队列
void QueueInit(Queue* q) {
	assert(q);
	q->back = q->front = NULL;
	q->size = 0;

}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data) {
	assert(q);
	QNode* newNode = buyNode(data);
	if (q->front == NULL) {
		q->front = newNode;
	}
	else {
		q->back->next = newNode;
	}
	q->back = newNode;
	q->size++;
}
// 队头出队列 
void QueuePop(Queue* q) {
	assert(q);
	if (QueueEmpty(q)) {
		assert(0);
	}
	else {
		q->front = q->front->next;
	}
	q->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q) {
	assert(q);
	assert(!QueueEmpty(q));
	return q->front->data;
}

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q) {
	assert(q);
	if (q->size == 0) {
		return 1;
	}
	else {
		return 0;
	}
}
// 销毁队列 
void QueueDestroy(Queue* q) {
	assert(q);
	QNode* cur = q->front;
	while (cur) {
		q->front = cur->next;
		free(cur);
		cur = q->front;
	}
	q->front = q->back = NULL;
	q->size = 0;
}



BTNode* buyBinaryTreeNode(int data) {
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL) {
		assert(0);
		return NULL;
	}
	newnode->left = NULL;
	newnode->right = NULL;
	newnode->data = data;
	return newnode;
}
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int *pi){
	BTNode* root = NULL;
	if (*pi < n && a[*pi] != '#') {
		root = buyBinaryTreeNode(a[*pi]);
		++(*pi);
		root->left = BinaryTreeCreate(a, n, pi);
		++(*pi);
		root->right = BinaryTreeCreate(a, n, pi);
	}
	return root;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root) {
	assert(root);
	if (*root) {
		BinaryTreeDestory(&(*root)->left);
		BinaryTreeDestory(&(*root)->right);
		free(*root);
		*root=NULL;
	}
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root) {
	if (NULL == root) {
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	if (root->left==NULL && root->right==NULL) {
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k) {
	if(root == NULL || k < 1) {
		return 0;
	}
	if (k == 1 ) {
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1 );
}
int BinaryTreeHeight(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	int leftHeight = BinaryTreeHeight(root->left);
	int rightHeight = BinaryTreeHeight(root->right);
	if (leftHeight > rightHeight) {
		return leftHeight + 1;
	}
	else {
		return rightHeight + 1;
	}
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType data) {
	BTNode* ret = NULL;
	if (root == NULL) {
		return 0;
	}
	if (root->data == data) {
		return root;
	}
	ret = BinaryTreeFind(root->left, data);
	if ( ret ) {
		return ret;
	}
	return BinaryTreeFind(root->right, data);
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root) {
	if (root) {
		printf("%c ", root->data);
		BinaryTreePrevOrder(root->left);
		BinaryTreePrevOrder(root->right);
	}
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root) {
	if (root) {
		BinaryTreeInOrder(root->left);
		printf("%c ", root->data);
		BinaryTreeInOrder(root->right);
	}
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root) {
	if (root) {
		BinaryTreePostOrder(root->left);
		BinaryTreePostOrder(root->right);
		printf("%c ", root->data);
	}
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root) {
	if (NULL == root) {
		assert(0);
	}
	Queue q;
    QueueInit(&q);
	QueuePush(&q, root);
	while(!QueueEmpty(&q)) {
		root = QueueFront(&q);
		printf("%c ", root->data);
		QueuePop(&q);
		if (root->left) {
			QueuePush(&q,root->left);
		}
		if (root->right) {
			QueuePush(&q, root->right);
		}
	}
	QueueDestroy(&q);
}
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root) {
	if (NULL == root) {
		return 0;
	}
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q)) {
		root = QueueFront(&q);
		QueuePop(&q);
		if ((root->left != NULL && root->right == NULL)) {
			QueueDestroy(&q);
			return 0;
		}
		if (root->left != NULL) {
			QueuePush(&q, root->left);
		}
		if(root->right != NULL){
			QueuePush(&q, root->right);
		}
	}
	QueueDestroy(&q);
	return 1;
}
int main() {
	BTDataType str[20] = "ABD##E#H###CF##G##";
	int n = strlen(str);
	printf("%d\n", n);
	puts(str);
	int pi = 0;
	BTNode* root = BinaryTreeCreate(str, n, &pi);
	BinaryTreePrevOrder(root); 
	printf("\n");
	BinaryTreeInOrder(root);
	printf("\n");
	printf("%d", BinaryTreeSize(root));
	printf("\n");
	printf("%d\n", BinaryTreeLeafSize(root));
	printf("%d\n", BinaryTreeLevelKSize(root,3));
	printf("%d\n", BinaryTreeHeight(root));
	if (BinaryTreeFind(root, 'A')) {
		printf("A in tree\n");
	}
	else {
		printf("A not in tree\n");
	}
	BinaryTreeLevelOrder(root);
	printf("\n");
	if (BinaryTreeComplete(root)) {
		printf("this tree is complete\n");
	}
	else {
		printf("this tree is not complete\n");
	}
	BinaryTreeDestory(&root);
	return 0;
}
